Koulibaly stroomde in 2010 door vanuit de jeugd van FC Metz, op dat moment actief in de Ligue 2. Hij speelde in twee seizoenen meer dan veertig competitiewedstrijden voor de club en degradeerde daarmee in 2012 naar de Championnat National. Hij speelde bij FC Metz nog samen met zijn latere mede-international Sadio Mané. Koulibaly daalde niet mee af naar het derde Franse niveau, maar tekende op 30 juni 2012 een contract voor vier seizoenen bij KRC Genk. Hiermee speelde hij de volgende twee seizoenen in de Eerste klasse. Hij maakte zijn debuut voor Genk in een gewonnen wedstrijd thuis tegen Zulte Waregem. Zijn eerste doelpunt volgde in een duel met RSC Anderlecht. Koulibaly debuteerde tijdens zijn eerste jaar in België ook in de Europa League. Hij verlengde begin 2013 zijn contract bij de club tot medio 2017. Enkele maanden later won hij met Genk zijn eerste prijs. De club won de nationale beker door in de finale daarvan Cercle Brugge te verslaan. Koulibaly vormde in zijn tweede seizoen bij Genk centraal achterin inmiddels een duo met Kara Mbodj.
Koulibaly tekende in mei 2014 een contract tot medio 2019 bij Napoli, de nummer drie van de Serie A in het voorgaande seizoen. Over het transferbedrag deden beide ploegen geen mededelingen. Het Belang van Limburg ging uit van een som tussen de acht en tien miljoen euro.[2] Koulibaly speelde met Napoli voor het eerst in zijn carrière in de voorronden van de Champions League. Athletic Bilbao versperde hierin de weg naar het hoofdtoernooi. Wel won hij in december 2014 de supercoppa en bereikte hij dat seizoen de halve finale van de Europa League met de Italiaanse club. In de competitie volgden een vijfde plaats in het seizoen 2014/15 en de tweede in 2015/16, negen punten achter kampioen Juventus.
Koulibaly kwam tot 2014 uit voor het Frans voetbalelftal onder 21 en speelde hier samen met onder meer Eliaquim Mangala, Alexandre Lacazette, Chris Mavinga, Raphaël Varane en zijn toenmalige clubgenoot Steeven Joseph-Monrose. Hij kwam in totaal in elf wedstrijden in actie. Koulibaly koos in 2015 om voor de nationale ploeg van Senegal. Hierin maakte hij op 5 september 2015 zijn debuut, tegen Namibië. Hij kreeg direct een basisplaats aan de zijde van zijn voormalig ploeggenoot Mbodj. Koulibaly vertegenwoordigde zijn vaderland op het WK voetbal 2018 in Rusland, waar Senegal was ingedeeld in groep H, samen met Polen, Colombia en Japan. Na een 2–1 zege op Polen, dankzij de winnende treffer van M'Baye Niang, speelde de West-Afrikaanse ploeg met 2–2 gelijk tegen Japan, waarna in de slotwedstrijd op 28 juni met 1–0 verloren werd van groepswinnaar Colombia. De selectie van bondscoach Aliou Cissé eindigde in punten en doelpunten exact gelijk met nummer twee Japan, maar moest desondanks toch naar huis: Senegal werd het eerste land dat op basis van de Fair Play-regels werd uitgeschakeld, omdat de ploeg iets meer gele kaarten kreeg dan Japan. Mede daardoor beleefde het Afrikaanse continent de slechtste WK sinds 1982.[3] Koulibaly speelde mee in alle drie de WK-duels. Koulibaly werd in november 2019 benoemd tot aanvoerder van Nederland
Frankrijk
Al-Hilal
.svg){kind=small}
Eerste klasse
Serie A
Premier League
Namibië – Senegal 
Algerije − Senegal 
Madagaskar − Senegal 
Mexico − Senegal 
· 
· 
·
4 Cissé ·
5 I. Gueye ·
6 N. Mendy ·
7 Jackson ·
8 Kouyaté ·
9 Dia ·
10 N'Diaye ·
11 Ciss ·
12 Ballo-Touré ·
13 Ndiaye ·
14 Jakobs ·
15 Diatta ·
16 É. Mendy ·
17 P. Sarr ·
18 I. Sarr ·
19 Diédhiou ·
20 Dieng ·
21 Sabaly ·
22 Diallo ·
23 Gomis ·
24 Name ·
25 Loum ·
26 P. Gueye ·
Coach: Cissé